/*
 * unionfind_test.cpp
 *
 *  Created on: Jan 2, 2014
 *      Author: amatzlia
 */

// A union by rank and path compression based program to detect cycle in a graph
#include <iostream>
#include <stdlib.h>
#include <string.h>
using std::cout;
using std::endl;
#include "../unionFind.hpp"
#include "test_utilities.hpp"

namespace unionFindTest {

	// a structure to represent an edge in graph
	struct Edge
	{
		int src, dest;
	};

	// a structure to represent a graph
	struct Graph
	{
		// V-> Number of vertices, E-> Number of edges
		int V, E;

		// graph is represented as an array of edges
		struct Edge* edge;
	};

	// Creates a graph with V vertices and E edges
	struct Graph* createGraph(int V, int E)
	{
		struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
		graph->V = V;
		graph->E = E;

		graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

		return graph;
	}

	// The main function to check whether a given graph contains cycle or not
	int isCycle(struct Graph* graph)
	{
		int V = graph->V;
		int E = graph->E;

		UnionFind uf(V);

		// Iterate through all edges of graph, find sets of both
		// vertices of every edge, if sets are same, then there is
		// cycle in graph.
		for (int e = 0; e < E; ++e)
		{
			int x = uf.find(graph->edge[e].src);
			int y = uf.find(graph->edge[e].dest);

			if (x == y)
				return 1;

			uf.unite(x, y);
		}
		return 0;
	}

	void test1() {
		/* Let us create following graph
			 1
			 |  \
			 |    \
			 2-----3 */

		int V = 3, E = 3;
		struct Graph* graph = createGraph(V, E);

		// add edge 1-2
		graph->edge[0].src = 1;
		graph->edge[0].dest = 2;

		// add edge 2-3
		graph->edge[1].src = 2;
		graph->edge[1].dest = 3;

		// add edge 1-3
		graph->edge[2].src = 1;
		graph->edge[2].dest = 3;

		if (!isCycle(graph))
			std::cout << "FAILURE: Graph doesn't contain cycle" << endl;
		
		free(graph->edge);
		free(graph);
	}

	void test2() {
		const int size = 10;
		UnionFind ds(size);

		ASSERT_THROWS(InvlidIdException, ds.unite(1, 0));
		ASSERT_THROWS(InvlidIdException, ds.find(0));
		ASSERT_THROWS(InvlidIdException, ds.find(size + 1));
		ASSERT_NO_THROW(ds.unite(size, size));

		for (int i = 1; i <= size; ++i) {
			ASSERT_EQUALS(i, ds.find(i));
		}

		ds.unite(2, 1);
		ASSERT_EQUALS(2, ds.find(1));
		ASSERT_EQUALS(2, ds.find(2));
		for (int i = 3; i <= size; ++i) {
			ASSERT_EQUALS(i, ds.find(i));
		}

		ASSERT_THROWS(InvlidIdException, ds.find(size + 1));
		ASSERT_THROWS(InexistentSetException, ds.unite(1, 2));

		ds.unite(3, 2);
		ASSERT_EQUALS(3, ds.find(1));
		ASSERT_EQUALS(3, ds.find(2));
		ASSERT_EQUALS(3, ds.find(3));
		for (int i = 4; i <= size; ++i) {
			ASSERT_EQUALS(i, ds.find(i));
		}

		ds.unite(7, size);
		ASSERT_EQUALS(7, ds.find(size));
		ASSERT_EQUALS(7, ds.find(7));
		ASSERT_EQUALS(3, ds.find(1));
		ASSERT_EQUALS(3, ds.find(2));
		ASSERT_EQUALS(3, ds.find(3));
		for (int i = 4; i <= size - 1; ++i) {
			if (7 != i) {
				ASSERT_EQUALS(i, ds.find(i));
			}
		}

		ds.unite(3, 7);
		ASSERT_EQUALS(3, ds.find(size));
		ASSERT_EQUALS(3, ds.find(7));
		ASSERT_EQUALS(3, ds.find(1));
		ASSERT_EQUALS(3, ds.find(2));
		ASSERT_EQUALS(3, ds.find(3));
		for (int i = 4; i <= size - 1; ++i) {
			if (7 != i) {
				ASSERT_EQUALS(i, ds.find(i));
			}
		}

		ASSERT_NO_THROW(ds.unite(8, 8));
	}

	// Uncomment to run

	void run_unionFind_tests()
	{
		RUN_TEST(test1);
		RUN_TEST(test2);
	}

}